﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace T16_Generic
{
    class Program
    {
        static void Main(string[] args)
        {
            //泛型具体：类型安全
            BTreeNode<string> root = new BTreeNode<string>("北京");
            root.Left = new BTreeNode<string>("石家庄");
            root.Right = new BTreeNode<string>("济南");
            root.Left.Left = new BTreeNode<string>("太原");
            root.Left.Right= new BTreeNode<string>("郑州");
            root.Right.Right= new BTreeNode<string>("徐州");
            root.Right.Left= new BTreeNode<string>("青岛");
            Console.WriteLine("\n先序遍历:");
            root.PreorderTraverse();
            Console.WriteLine("\n中序遍历:");
            root.InorderTraverse();
            Console.WriteLine("\n后序遍历:");
            root.PostorderTraverse();

            BTreeNode<int> root2 = new BTreeNode<int>(0);
            root2.Left = new BTreeNode<int>(-1);
            root2.Right= new BTreeNode<int>(1);
            root2.Right.Right = new BTreeNode<int>(2);
            Console.WriteLine("\n中序遍历:");
            root2.InorderTraverse();
            BTreeNode<int> node = root2 << 2;
            Console.WriteLine(node);
            Console.WriteLine("\n中序遍历:");
            node.InorderTraverse();
            Console.ReadKey();
        }
        ///<summary>
        ///二叉树泛型实现
        /// </summary>
        /// <typeparam name="=T"></typeparam>
        public class BTreeNode<T>
        {
            private T data;
            public T Data
            {
                get { return data; }
                set
                {
                    if (!data.Equals(value))//说明T必须实现了Equals
                        data = value;
                }
            }
            //递归定义
            public BTreeNode<T> Left { get; set; }
            public BTreeNode<T> Right { get; set; }

            public BTreeNode(T data)
            {
                this.data = data;
            }
            /// <summary>
            /// 先序遍历
            /// </summary>
            public void PreorderTraverse()
            {
                Console.Write(this.data.ToString()+' ');
                if (this.Left != null)
                    this.Left.PreorderTraverse();
                if (this.Right != null)
                    this.Right.PreorderTraverse();
            }
            /// <summary>
            /// 中序遍历
            /// </summary>
            public void InorderTraverse()
            {
                if (this.Left != null)
                    this.Left.InorderTraverse();
                Console.Write(this.data.ToString() + ' ');
                if (this.Right != null)
                    this.Right.InorderTraverse();
            }
            /// <summary>
            /// 后序遍历
            /// </summary>
            public void PostorderTraverse()
            {
                if (this.Left != null)
                    this.Left.PostorderTraverse();
                if (this.Right != null)
                    this.Right.PostorderTraverse();
                Console.Write(this.data.ToString() + ' ');
            }

            /// <summary>
            /// 获取指定第N层的左子树
            /// </summary>
            /// <param name="node"></param>
            /// <param name="n"></param>
            /// <returns></returns>
            public static BTreeNode<T> operator << (BTreeNode<T> node,int n)
            {
                for(int i=0;i<n&&node.Left !=null;i++)
                {
                    node = node.Left;
                }
                return node;
            }

            /// <summary>
            /// 获取指定第N层的右子树
            /// </summary>
            /// <param name="node"></param>
            /// <param name="n"></param>
            /// <returns></returns>
            public static BTreeNode<T> operator >> (BTreeNode<T> node, int n)
            {
                for (int i = 0; i < n && node.Right != null; i++)
                {
                    node = node.Right;
                }
                return node;
            }
            public override string ToString()
            {
                return data.ToString();
            }
        }
    }
}
